package com.algorithm.ch1.yjx.array;

import java.util.HashSet;
import java.util.Set;

/**
 * @author yuanjianxin
 * @date 2018/8/14 17:33
 */
public class IsValidSudoku {

    public static void main(String[] args) {
        char[][] arr = {
                {'5', '3', '.', '.', '7', '.', '.', '.', '.'},
                {'6', '.', '.', '1', '9', '5', '.', '.', '.'},
                {'.', '9', '8', '.', '.', '.', '.', '6', '.'},
                {'8', '.', '.', '.', '6', '.', '.', '.', '3'},
                {'4', '.', '.', '8', '.', '3', '.', '.', '1'},
                {'7', '.', '.', '.', '2', '.', '.', '.', '6'},
                {'.', '6', '.', '.', '.', '.', '2', '8', '.'},
                {'.', '.', '.', '4', '1', '9', '.', '.', '5'},
                {'.', '.', '.', '.', '8', '.', '.', '7', '9'}
        };
        char[][] arr1 = {
                {'8', '3', '.', '.', '7', '.', '.', '.', '.'},
                {'6', '.', '.', '1', '9', '5', '.', '.', '.'},
                {'.', '9', '8', '.', '.', '.', '.', '6', '.'},
                {'8', '.', '.', '.', '6', '.', '.', '.', '3'},
                {'4', '.', '.', '8', '.', '3', '.', '.', '1'},
                {'7', '.', '.', '.', '2', '.', '.', '.', '6'},
                {'.', '6', '.', '.', '.', '.', '2', '8', '.'},
                {'.', '.', '.', '4', '1', '9', '.', '.', '5'},
                {'.', '.', '.', '.', '8', '.', '.', '7', '9'}
        };

        System.out.println(isValidSudoku2(arr));
        System.out.println(isValidSudoku2(arr1));


    }

    public static boolean isValidSudoku(char[][] arr) {
        Set<Integer> rowSet = new HashSet<>();
        Set<Integer> colSet = new HashSet<>();
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr.length; j++) {
                //行数据
                char rowChar = arr[i][j];
                //列数据
                char colChar = arr[j][i];
                if (repeat(rowSet, rowChar)) {
                    return false;
                }
                if (repeat(colSet, colChar)) {
                    return false;
                }

                if (i % 3 == 0 && j % 3 == 0) {
                    Set<Integer> tempSet = new HashSet<>();
                    for (int k = i; k <= i + 2; k++) {
                        for (int l = j; l <= j + 2; l++) {
                            char ch = arr[k][l];
                            if (repeat(tempSet, ch)) {
                                return false;
                            }
                        }
                    }
                }
            }

            rowSet.clear();
            colSet.clear();
        }
        return true;
    }


    public static boolean repeat(Set<Integer> set, char ch) {
        if (ch == '.') {
            return false;
        }
        int num = ch - '0';
        if (set.contains(num)) {
            return true;
        } else {
            set.add(num);
            return false;
        }
    }


    public static boolean isValidSudoku2(char[][] arr) {
        int length = arr.length;
        boolean[][] row = new boolean[length][length];
        boolean[][] col = new boolean[length][length];
        boolean[][] square = new boolean[length][length];

        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr.length; j++) {
                if (arr[i][j] == '.') {
                    continue;
                }
                //1-9的字符减去字符'1' 结果为0-8,当做坐标index
                int index = arr[i][j] - '1';

                //有一个为true,说明已经有设置过值，存在相同index,即存在重复的数
                if (row[i][index] || col[index][j] || square[3 * (i / 3) + j / 3][index]) {
                    return false;
                }
                row[i][index] = true;
                col[index][j] = true;
                //将9个3x3变成一个2维数组，i,j变成0,1,2,3...8当做横坐标
                square[3 * (i / 3) + j / 3][index] = true;
            }
        }
        return true;
    }


}
